package com.eatme.leetcode.problems;

import java.util.Arrays;

/**
 *  875. 爱吃香蕉的珂珂 koko-eating-bananas
 */
public class Solution1011 {

    public int shipWithinDays(int[] weights, int days) {
        int l = Arrays.stream(weights).max().getAsInt();
        int r = Arrays.stream(weights).sum();
        while(l < r){

            int mid = l + (r - l) / 2;

            // 如果传送带运载能力是 mid，运完货物需要的天数小于等于 D
            // 那么 mid 就是一个可能的解，但是，我们还要找，看有没有更小的解
            // 所以，调整右边界，r = mid。
            // 注意，mid 要包含在搜索范围里，因为 mid 是问题的解
            if(days(weights, mid) <= days)
                r = mid;
                // 否则的话，运完货物需要的天数大于 D
                // 我们就需要加大传送带的运载能力，以在更短的时间里运送所有货物
                // 因此，我们调整左边界，l = mid + 1。
                // 注意，mid 不再包含在搜索空间中，因为此时，mid 不是问题的解
            else
                l = mid + 1;

            // 在决定好搜索空间的调整方式后，我们可以试验一下，如果 l， r 相邻，是否会出现死循环？
            // 在这个例子中，因为下取整以后，在 l 和 r 相临时，mid 为 l。而对 l 的更新，是 mid + 1
            // 所以保证了在这种情况下，搜索空间会继续缩小，不会产生死循环
            // 因此，使用下取整来计算 mid 是可以的
        }
        return l;
    }

    private int days(int[] weights, int k) {
        // cur 为当前传送带的载重；res 为最终的返回结果
        int cur = 0, res = 0;

        // 遍历 weights 中的每一个元素
        for(int weight: weights)
            // 如果当前的重量加上当前的货物没有超过 k，
            // 把当前货物重量加在 cur 上
            if(cur + weight <= k) cur += weight;
                // 否则的话，相当于从当前的货物开始，我们需要新的一天运输
                // res ++，同时，cur 更新为当前的重量
            else{
                res ++;
                cur = weight;
            }

        // 最后还要做一次 res ++，因为在这里 cur 肯定不为零，还记录着最后一天需要运送的货物重量
        // 最后一天，要加到 res 中，所以 res ++
        res ++;

        return res;
    }

    public static void main(String[] args) {
        int[] weights = {3,2,2,4,1,4};
        int days = 3;
        System.out.println(new Solution1011().shipWithinDays(weights,days));
    }
}